"""
单调栈
记住框架
"""

class Solution(object):
    def nextGreaterElement(self, nums1, nums2):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :rtype: List[int]
        """
        answer = self.monotone_stack(nums2)
        res = []
        for i, num in enumerate(nums1):
            index  = nums2.index(num)
            res.append(answer[index])
        return res

    def monotone_stack(self, nums2):
        # 存答案的数组
        answer = [-1 for _ in range(len(nums2))]

        # 单调栈
        mono_stack = []

        for i in range(len(nums2) - 1, -1, -1): # 倒着向栈中放元素
            while mono_stack and mono_stack[-1] <= nums2[i]:    # 倒着向栈中放元素，保证单调递减的栈
                mono_stack.pop()    # 由于当前位置nums[i]更大或者相等，所以需要剔除单调栈的元素，保证栈顶元素始终大于当前数组nums2[i]
            
            # 如果单调栈为空，就向ans加入-1，否则加入栈顶元素;栈顶元素的物理含义就是站在当前位置能看到的最大值
            answer[i] = -1 if not mono_stack else mono_stack[-1]
            # 当前元素先进入单调栈，判定其身高，来组成单调栈
            mono_stack.append(nums2[i])
        return answer